# Definition for a undirected graph node
class UndirectedGraphNode(object):
    def __init__(self, x):
        self.label = x
        self.neighbors = []

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        lDict = {}
        def build(node):
            clone = UndirectedGraphNode(node.label)
            lDict.update({node.label:clone})
            for neighbor in node.neighbors:
                if neighbor.label in lDict:
                    clone.neighbors.append(lDict[neighbor.label])
                else:
                    clone.neighbors.append(build(neighbor))
            return clone
        return build(node) if node else None